home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / systems / mac / oztex-german / OzTeX-1.4d.sit.bin / OzTeX 1.4 / Macros mit Doku / TREE / CLASSES.TEX next >
Text File  |  1991-10-05  |  9KB  |  106 lines
  1.                                                                                 
  2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  3. %%% Complete binary trees                                                  %%%  
  4. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  5.                                                                                 
  6. % The macro \b@nary{<number>} expands to the description of a complete          
  7. % binary tree with <number> many internal nodes, where each level is filled with
  8. % the maximal number of internal nodes, and the last level of internal nodes    
  9. % is filled from left to right.                                                 
  10.                                                                                 
  11. \newcount\b@nno % number of nodes                                               
  12. \newcount\b@nlv % number of complete levels                                     
  13. \newcount\b@ndl % number of nodes on incomplete level                           
  14.                                                                                 
  15. \def\ld(#1,#2,#3){% #1, #2, and #3 must be counter registers.                   
  16.                   % #1 is the input, #1 must be >= 1.                           
  17.                   % \ld makes the following assignments:                        
  18.                   % #2:=|_log_2(#1)_|, #3:=2^#2.                                
  19.                   % The contents of #1 is destroyed during the computation.     
  20.      #2=0 #3=1                                                                  
  21.        \loop\ifnum #1>\@ne\relax                                                
  22.             \divide #1 by\tw@ % this is integer division                        
  23.             \advance #2 by\@ne                                                  
  24.             \multiply #3 by\tw@                                                 
  25.      \repeat}                                                                   
  26.                                                                                 
  27. \def\b@nary#1{% draws a complete binary tree with #1 internal nodes,            
  28.            % a complete binary tree with N internal nodes has                   
  29.            % lv:=|_log_2(N+1)_| many                                            
  30.            % complete level of binary nodes and dl:=N-2^{lv}+1 many internal    
  31.            % nodes on an incomplete level.                                      
  32.      \b@nno=#1\relax\advance\b@nno by \@ne                                      
  33.      \ld(\b@nno,\b@nlv,\b@ndl)%                                                 
  34.      \b@ndl=-\b@ndl\advance\b@ndl by #1\advance\b@ndl by\@ne                    
  35.      \b@n}                                                                      
  36.                                                                                 
  37. \def\b@n{%                                                                      
  38.      \ifnum\b@nlv>\@ne                                                          
  39.            \advance\b@nlv by-\@ne                                               
  40.            \b@n                                                                 
  41.            \b@n                                                                 
  42.            \advance\b@nlv by\@ne                                                
  43.            \node{}                                                              
  44.       \else\ifnum\b@ndl>\@ne                                                    
  45.                  \advance\b@ndl by-\tw@                                         
  46.                  \node{\le@f\external}\node{\le@f\external}\node{}%             
  47.                  \node{\le@f\external}\node{\le@f\external}\node{}%             
  48.                  \node{}%                                                       
  49.             \else\ifnum\b@ndl=\@ne                                              
  50.                        \advance\b@ndl by-\@ne                                   
  51.                        \node{\le@f\external}\node{\le@f\external}\node{}%       
  52.                        \node{\le@f\external}%                                   
  53.                        \node{}%                                                 
  54.                   \else\node{\le@f\external}\node{\le@f\external}\node{}%       
  55.                     \fi                                                         
  56.               \fi                                                               
  57.         \fi}                                                                    
  58.                                                                                 
  59. \def\circleleaves{\def\le@f{\type{circle}}}                                     
  60. \def\squareleaves{\def\le@f{\type{square}}}                                     
  61.                                                                                 
  62. \newcount\no@                                                                   
  63. \def\no#1{\no@=#1\relax}                                                        
  64.                                                                                 
  65. \def\binary#1{%                                                                 
  66.      \no{1}\circleleaves                                                        
  67.      #1%                                                                        
  68.      \b@nary{\no@}}                                                             
  69.                                                                                 
  70. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  71. %%% Fibonacci trees                                                        %%%  
  72. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  73.                                                                                 
  74. % \f@b expands to the description of a Fibonacci tree                           
  75. % of height \f@bht.                                                             
  76.                                                                                 
  77. \newcount\f@bht                                                                 
  78.                                                                                 
  79. \def\f@b{% draws a Fibonacci tree of depth #1                                   
  80.      \ifnum\f@bht>1                                                             
  81.            \advance\f@bht by-\@ne\f@b\advance\f@bht by\@ne                      
  82.            \advance\f@bht by-\tw@\f@b\advance\f@bht by\tw@                      
  83.            \ifunn@des\node{\unary}                                              
  84.                   \fi                                                           
  85.            \node{\lefttop}                                                      
  86.       \else\ifnum\f@bht=1                                                       
  87.                  \node{\external\le@f}                                          
  88.                  \node{\external\le@f}                                          
  89.                  \node{}                                                        
  90.             \else\node{\external\le@f}                                          
  91.               \fi                                                               
  92.         \fi}                                                                    
  93.                                                                                 
  94. \newif\ifunn@des                                                                
  95.                                                                                 
  96. \let\unarynodes\unn@destrue                                                     
  97. \def\hght#1{\f@bht=#1\relax}                                                    
  98.                                                                                 
  99. \def\fibonacci#1{%                                                              
  100.      \hght{0}\unn@desfalse\circleleaves                                         
  101.      #1%                                                                        
  102.      \f@b}                                                                      
  103.                                                                                 
  104.                                                                                 
  105. %                                                                               
  106.